#include "main/utils.h"
using namespace std;

// *****************solution1**********************
void findCircle(const vector<vector<bool>>& friends,
                vector<bool>& visited,
                int i) {
  visited[i] = true;
  queue<int> queue;
  queue.push(i);
  while (!queue.empty()) {
    int cur = queue.front();
    queue.pop();
    for (int j = 0; j < friends.size(); ++j) {
      if (!visited[j] && friends[cur][j]) {
        queue.push(j);
        visited[j] = 1;
      }
    }
  }
}

int findCircleNum1(const vector<vector<bool>>& friends) {
  int num = friends.size();
  vector<bool> visited(num, 0);
  int result = 0;
  for (int i = 0; i < num; ++i) {
    if (!visited[i]) {
      findCircle(friends, visited, i);
      ++result;
    }
  }
  return result;
}

// *****************solution2**********************
int findFather(vector<int>& fathers, int i) {
  if (fathers[i] != i) {
    fathers[i] = findFather(fathers, fathers[i]);
  }
  return fathers[i];
}

bool merge(vector<int>& fathers, int i, int j) {
  int father_i = findFather(fathers, i);
  int father_j = findFather(fathers, j);
  if (father_i == father_j)
    return false;
  fathers[father_i] = father_j;
  return true;
}

int findCircleNum2(const vector<vector<bool>>& friends) {
  int num = friends.size();
  vector<int> fathers;
  for (int i = 0; i < num; ++i) {
    fathers.push_back(i);
  }
  int count = num;
  for (int i = 0; i < num; ++i) {
    for (int j = i + 1; j < num; ++j) {
      if (friends[i][j] && merge(fathers, i, j)) {
        --count;
      }
    }
  }
  return count;
}

int main() {
  vector<vector<bool>> friends = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
  cout << findCircleNum1(friends) << endl;
  cout << findCircleNum2(friends) << endl;

  return 0;
}
